class Solution {
public:
    // 卡特兰数 h(n)=h(n-1)*(4*n-2)/(n+1)
    // h(0) = 1, h(1) = 1
    int numTrees(int n) {

        long long h = 1;
        long long i = 2;
        
        while(i <= n){
            h = h * (4 * i - 2) / (i + 1);
            ++i;
        }

        return h;

    }
};